package graph.tree;

import graph.weight.Edge;
import graph.weight.EdgeWeightedGraph;
import linear.Queue;
import priority.IndexMinPriorityQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 最小生成树算法 prim
 */
public class PrimMST {
    // 两点间最短边
    private Edge[] edgeTo;
    // 两点间最短边权重
    private double[] distTo;
    private boolean[] marked;

    private IndexMinPriorityQueue<Double> pq;

    public PrimMST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new IndexMinPriorityQueue<>(G.V());


        for (int i = 0; i < G.V(); i++) {
            // 无穷大
            distTo[i] = Double.POSITIVE_INFINITY;
        }

        // 默认0顶点开始，初始化
        distTo[0] = 0.0;
        // 初始化列队
        pq.insert(0, 0.0);

        while (!pq.isEmpty()) {
            visit(G, pq.delMin());
        }


    }

    private void visit(EdgeWeightedGraph G, int v) {
        marked[v] = true;
        // 遍历当前结点的邻接表
        for (Edge e : G.adj(v)) {
            int w = e.other(v);
            if (marked[w]) {
                continue;
            }
            if (e.weight() < distTo[w]) {
                edgeTo[w] = e;
                distTo[w] = e.weight();

                if (pq.contains(w)) {
                    pq.changeItem(w, e.weight());
                } else {
                    pq.insert(w, e.weight());
                }
            }
        }
    }

    public Queue<Edge> edges() {
        Queue<Edge> edges = new Queue<>();
        for (int i = 0; i < marked.length; i++) {
            if (edgeTo[i] != null) {
                edges.enqueue(edgeTo[i]);
            }
        }
        return edges;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new
                InputStreamReader(PrimMST.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));
        //读取顶点数目，初始化EdgeWeightedGraph图
        int number = Integer.parseInt(reader.readLine());
        EdgeWeightedGraph G = new EdgeWeightedGraph(number);
        //读取边的数目
        int edgeNumber = Integer.parseInt(reader.readLine());
        //循环读取每一条边，并调用addEdge方法
        for (int i = 0; i < edgeNumber; i++) {
            String line = reader.readLine();
            int v = Integer.parseInt(line.split(" ")[0]);
            int w = Integer.parseInt(line.split(" ")[1]);
            double weight = Double.parseDouble(line.split(" ")[2]);
            G.addEdge(new Edge(v, w, weight));
        }

        //构建PrimMST对象
        PrimMST mst = new PrimMST(G);
        //获取最小生成树的边
        Queue<Edge> edges = mst.edges();
        //打印输出

        for (Edge e : edges) {
            System.out.println(e.either() + "-" + e.other(e.either()) + "::" + e.weight());
        }

    }


}
